package Leetcode.数组字符串;

/**
 * 现有两个等长的数组A和B，里面存放的是整型数据。现在分别要从数组A中取m个数，
 * 数组B中取n个数，两个数组中所取数的数组下标不能相同。
 * 要求计算所取整数之和的最大值
 */
public class MaxSumCalculator {
    /**
     * TODO:这个思路有问题
     *
     * 假设数组 A 的长度为 m，数组 B 的长度为 n。
     *
     * 我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从数组 A 的前 i 个数和数组 B 的前 j 个数中所取整数之和的最大值。
     *
     * 动态规划的边界条件为 dp[0][0] = 0，表示从两个空数组中取整数和为 0。
     *
     * 然后，我们可以使用以下递推关系来计算 dp[i][j]：
     *
     * dp[i][j] = max(dp[i-1][j] + A[i-1], dp[i][j-1] + B[j-1])
     *
     * 其中，dp[i-1][j] + A[i-1] 表示从数组 A 中取第 i 个数，dp[i][j-1] + B[j-1] 表示从数组 B 中取第 j 个数。我们需要选择这两个值中的较大值作为 dp[i][j] 的值。
     *
     * 最终，dp[m][n] 即为所求的结果，表示从数组 A 和数组 B 中取 m 个数和 n 个数的最大和。
     * @param A
     * @param B
     * @param m
     * @param n
     * @return
     */
    public static int maxSum(int[] A, int[] B, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j] + A[i - 1], dp[i][j - 1] + B[j - 1]);
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5};
        int[] B = {6, 7, 8, 9, 10};
        int m = 3;
        int n = 2;

        int result = maxSum(A, B, m, n);
        System.out.println(result);  // 输出：24
    }
}